package Sort;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int arr[]={4,6,8,5,9};
        heapSort(arr);

    }
    public static void heapSort(int[] arr){
        System.out.println(Arrays.toString(arr));
        int temp=0;
        System.out.println("堆排序");
    /*    adjustHeap(arr,1,arr.length);
        System.out.println(Arrays.toString(arr)+1);
        adjustHeap(arr,0,arr.length);
        System.out.println(Arrays.toString(arr)+2);
        */
        for (int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        System.out.println(Arrays.toString(arr));
        /**
         *变成大堆顶后 ，最大的就是最上面那个 ，将他沉底 ，重新adjust，不过adjust 长度--
         */
        for (int j=arr.length-1;j>=0;j--){
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,j);
            System.out.println(Arrays.toString(arr)+j);
        }

    }
    public static void adjustHeap(int[] arr,int i,int length){
        int temp=arr[i];//先取出当前元素保存在临时变量
        //开始调整
        //1. k=i*2+1  k是i的左子节点
        for (int k=i*2+1;k<length;k=k*2+1){
            //说明左子小于右子值
            if (k+1<length&&arr[k]<arr[k+1]){
                k++;//指向右节点
            }
            if (arr[k]>temp){
                arr[i]=arr[k];
                i=k;//指向k 循环比较。
            }else {
                break;
            }
            arr[k]=temp;
        }

    }
}
